New telecommunication services requiring the transport and switching of large amounts of data are being planned for the near future. Some possible applications for these services are LAN interconnection, motion video, and imaging. Two notable characteristics of these new services are their high bandwidth requirements (in the order of Megabits per second), and the bursty nature of their sources of information, which allows for easy packetization of the generated data.
Consequently, a new set of standards for a high speed, high performance packet network known as Broadband ISDN, or B-IDSN, are being developed in support of these new services. The B-ISDN standards call for the implementation of new packet multiplexing and switching techniques, referred to as Asynchronous Transfer Mode (ATM). In ATM, information is carried in packets of fixed size, presently equal to 53 octets, called cells. Those packets are individually labelled by appending addressing/multiplexing information into the first five octets of each cell. Packets from multiple sources are statistically multiplexed into a single transmission facility. The packets are identified by the contents of their headers rather than by their time position in the multiplexed stream. A single ATM transmission facility may carry hundreds of thousands of ATM cells per second.
A new generation of switching devices is needed to handle the high speed ATM streams. These devices perform the switching function in real time, by analyzing the information in the header of the incoming cells and routing them to the appropriate destination. Millions of cells per second need to be switched by a single device. New switching techniques that rely heavily on high density Application Specific Integrated Circuits can be applied to implementing ATM switches.
As stated above, streams of packets multiplexed in ATM form, arriving from a multiplicity of different sources, may be switched to one of a number of given destinations by ATM switching devices that interpret the addressing information in the packet headers. Unlike conventional synchronous time-division-multiplexing switches, in an ATM switch no attempt is made to organize the incoming packets in the time domain so as to avoid collisions between cells arriving at the same time, but in different inlets of the switch, when those cells are destined for the same output port of the switch. Consequently, collisions occur among cells that arrive to the switch at the same time carrying the same routing information in their headers. The ATM switch must provide a mechanism for resolving contentions for the same output among cells, by selecting one or more cells contending for delivery to the desired output according to some criteria such as cell priority.
In the event of multiple, simultaneous cell arrivals for the same destination, the ATM switch delivers one or more of the cells to the desired output and stores the remaining cells for delivery during subsequent switching intervals. It is not acceptable in the B-ISDN network to discard the undelivered cells. Therefore, it is necessary to provide sufficient storage, in the form of memory buffers, for the undelivered cells.
In the selection of an ATM switch architecture, two of the factors deciding the overall performance of the switch are the location of the cell buffers and the speed advantage of the switching fabric. The speed advantage of the switching fabric is defined as the ratio of cells that the fabric can deliver to the same output destination to the number of cells arriving at a single inlet in any given period of time. A switch fabric that can deliver, for instance, two cells to an outlet in the time that it takes for a cell to arrive at the switch enjoys a speed advantage of two.
Various combinations of buffering techniques and speed advantages have been proposed in the known state of the art. In one instance, cell buffering is provided solely at the input side of the ATM switch. The buffers are organized as FIFO queues where the incoming cells wait until they can be delivered to the desired output. One queue per input port to the switch is provided. The input queues are connected to a self-routing crossbar capable of delivering one cell per switching interval to each output (i.e., the speed advantage of the switch matrix is 1). Assuming a random distribution of destination addresses carried in the cell headers, the frequency of collisions among cells simultaneously attempting to reach the same destination limits the switch's throughput to about 0.586 Erlang. That is, a buffer overflow will occur if the inputs to the switch are loaded with cell traffic exceeding 0.586 Erlang intensity.
In another instance, a set of queues at the output side of an ATM switch of size N (N inputs by N outputs) are preceded by a switching fabric with a speed advantage equal to N, the switch size. In this way, no input buffering is required, since the switching fabric is capable of delivering N packets simultaneously present at the input side to any single destination. Output buffers are required to collect the bursts of up to N cells that may arrive at the output side of the switch while only one cell is delivered to each outlet per switching interval. This type of output buffering switch architecture is capable of handling a traffic intensity of 1 Erlang per switching port as long as the speed advantage of the fabric equals the switch size. In practice, this condition can only be maintained for small values of N (8 or 16). The throughput decays as larger switches are configured by interconnecting output buffer modules in some multiple-stage fashion.
Other switching techniques are possible. Integrating small crosspoints (e.g., 2 by 2 or 4 by 4) with buffers in some multistage interconnecting topology is one of those. The technique yields low switching throughputs and its hardware implementation is more complex than those described above. In most instances of multiple stage interconnecting arrangements whether input buffering, output buffering, or intermediate buffering is employed, the resulting switch is blocking, that is, the addition of a connection from an available inlet to an available outlet may not be possible due to the lack of an available internal link.
In addition to switching throughput, two other performance related variables need to be considered when discussing ATM switching techniques. One is cell loss, and the other is cell switching delay. Cell loss is caused by the finite size of the buffer pools forming the switch queues. Typical cell losses in input or output buffer ATM switches are in the range of 1e-06 (1 cell in 1 million) to 1e-09 (1 cell in 1 billion). These losses are relatively high by comparison to the error rates that can be expected from the fiber optic based facilities carrying the cells between switches.
Since ATM switching techniques are probabilistic in nature, cell switching delays will not be constant for all the cells arriving at the switch. Therefore, cell switching delays will be characterized by a mean value and a variance, the values of which will be dependent on the selection of the switching technique.
In B-ISDN, multiple grades of service may need to be offered in support of various forms of traffic requiring different levels of cell loss and propagation delay. It is known, for instance, that video connections can tolerate relatively large cell losses, but are very sensitive to delay variations from one cell to the next. Other forms of data traffic are more tolerant of large propagation delays and delay variance, but require very low cell losses. Finally, some forms of connection-oriented traffic (e.g., circuits) may require an ATM switch topology that is non-blocking, that is, a topology that permits the establishment of a new connection independent of the current state of occupation of the switching matrix.
Accordingly, there is a need in the art for a telecommunications switch and method of operation that allows for the passage through the switch of high volumes of information while incurring cell losses lower than those experienced by previous art. A further need exists in the art for an ATM switch that allows for large switching capacities with minimum propagation delays and delay variances, and that provides a mechanism for cell contention resolution. A further need exists in the art for a switch and method as discussed above that can handle multiple forms of traffic including forms that may require a non-blocking switching property.